/*
提交链接:https://leetcode.cn/problems/number-of-digit-one/
233. 数字 1 的个数
赖德檀 2024/12/04
*/

class Solution {
public:
    static const int MAX = 11;
    int ans[MAX][100];
    vector<int> arr;
    int dp(int n){
        if(!n)return 0;
        while(n){
            arr.push_back(n % 10);
            n /= 10;
        }
        int r = 0;
        int l = 0;
        int num = 0;
        for(int i = arr.size() - 1 ; i >= 0 ; --i){
            int x = arr[i];
            if(num > 0)
            {
                r += x*num*pow(10 , i);
            }
            for(int j = 0 ; j < x ; j++){
                r += ans[i + 1][j];
            }
            l = x;
            if(x == 1)
            {
                num++;
            }
        }
        r += num;
        return r;
    }
    int countDigitOne(int n) {
        for(int i = 0 ; i < 10 ; i++){
            ans[0][i] = 0;
        }
        for(int i = 1 ; i < MAX ; i++){
            for(int j = 0 ; j < 10 ; j++){
                for(int t = 0 ; t < 10 ; t++){
                    ans[i][j] += ans[i - 1][t];
                }
                ans[i][j] += j == 1 ? pow(10 , i - 1) : 0;
            }
        }
        return dp(n);
    }
};